//数组中的第k个最大数
https://leetcode.cn/problems/kth-largest-element-in-an-array/

class Solution {
public:
    int ret = INT_MIN;
    int findKthLargest(vector<int>& nums, int k) 
    {
        // int hashi[20001] = {0};
        // for(auto& e : nums)
        // {
        //     hashi[e+10000]++;
        // }
        // for(int i = 20000; i >= 0; i--)
        // {
        //     k -= hashi[i];
        //     if(k <= 0)
        //     {
        //         return i - 10000;
        //     }
        // }
        // return 0;   

        //快排 -> O(n)
        int n = nums.size();
        srand(time(nullptr));
        dfs(nums,k,0,n - 1);
        return ret;
    }

    void dfs(vector<int>& nums, int k,int begin, int end)
    {
        if(begin >= end)
        {
            ret = nums[begin];
            return;
        }

        int left = begin - 1;
        int right = end + 1;

        int pos = rand() % (end - begin + 1) + begin;
        int target = nums[pos]; //目标值
        int cur = begin;
        while(cur < right)
        {
            if(nums[cur] < target)
            {
                swap(nums[++left],nums[cur++]);         
            }
            else if(nums[cur] > target)
            {
                swap(nums[--right],nums[cur]);
            }
            else
            {
                cur++;
            }
        }
        int c = end - right + 1;
        int b = right - left - 1;
        int a = left - begin + 1;
        
        if(c >= k)
        {
            dfs(nums,k,right,end);
        }
        else if(c + b >= k)
        {
            ret = target;
        }
        else
        {
            dfs(nums,k - c - b,begin,left);
        }               
    }
};